/*************************************************
 *	文件名称：mydata.c
 *	文件说明：文件为动态单链线性表的函数实现文件
 *	程序平台：
 *	文件作者：Jason <jasonsunsoft@163.com>
 *	文件时间：2014年8月26日 17:47
*************************************************/
#include "mydata.h"

// 分配由p指向的值为e的结点，并返回OK；若分配失败，则返回ERROR
Status MakeNode(Link *p, ElemType e)
{
	(*p) = (Link) malloc(sizeof(LNode));
	if (*p)
	{
		(*p)->data = e;		//将数值传递给结点
		(*p)->next = NULL;	//将后继结点地址设置为空
		return OK;
	}
	else
		return ERROR;
}

// 释放p所指向的结点
void FreeNode(Link p)
{
	free(p);
}

//更新链表长度,更新尾结点位置的函数
void UpLinkLen(LinkList *L)
{
	int i = 0;
	Link p;
	p = L->head;
	while(p->next != NULL)
	{
		p = p->next;
		i++;
	}
	L->tail = p;
	L->len = i;
}


//构造一个空的线性表
Status InitList(LinkList *L)
{
	L->head = (Link)malloc(sizeof(LNode));
	if (!(L->head))
		return ERROR;
	L->head->next = NULL;	//设置头结点的下一个结点为空
	L->tail = L->head;
	L->len = 0;
	return OK;
}//InitList


Status ImportElem(LinkList *L, int n)
{
	int i;
	ElemType e;
	Link p, q;

	if (n > 0)
	{
		printf("enter 1st elem ");
		scanf("%d", &e);
		if (!MakeNode(&p, e))
			return ERROR;
		if (!InsFirst(L->head, p))
			return ERROR;
		L->len = 1;
		L->tail = p;
	}

	for (i = 1; i < n; i++)
	{
		printf("enter %dst elem ",i+1);
		scanf("%d", &e);
		if (!MakeNode(&p, e))
			return ERROR;
		q = L->tail;
		if (!InsAfter(L, &q, p))
			return ERROR;
	}
	printf("ImportElem ended\n");

	return OK;

}



//销毁线性链表L，L不再存在
Status DestroyList(LinkList *L)
{
	if (L->len)
		return ERROR;
	FreeNode(L->head);
	free(L);
	return OK;
}//DestroyList

//将线性链表L重置为空表，并释放原链表的结点空间
Status ClearList(LinkList *L)
{
	Link p, q, r;

	r = L->head->next;
	while (r)
	{
		p = r->next;
		FreeNode(r);
		r = p;
		L->len --;
	}
	if (L->len == 0)
	{
		L->head->next = NULL;
		L->tail = L->head;
		return OK;
	}
	else
		return ERROR;
}//ClearList_Sq

//已知h指向线性链表的头结点，将s所指结点插入在第一个节点之前
Status InsFirst(Link h, Link s)
{
	if ((!s) && (!h->next))
		return ERROR;
	s->next = h->next;
	h->next = s;
	return OK;
}//InsFirst

//已知h指向线性链表的头结点，删除链表中的第一个结点并以q返回
Status DelFirst(Link h, Link *q)
{
	if (!h->next)
		return ERROR;
	*q = h->next;
	h->next = h->next->next;
	(*q)->next = NULL;
	return OK;
}

//将指针s所指（彼此以指针相连）的一串结点链表在线性表L的最后一个结点
//之后，并改变链表L的尾指针指向新的尾结点
Status Append(LinkList *L, Link s)
{
	L->tail->next = s;
	while (L->tail->next)
	{
		L->tail = L->tail->next;
		L->len++;
	}
	return OK;

}

//删除线性链表L中的尾结点并且以q返回，改变链表L的尾指针指向新的尾结点
Status Remove(LinkList *L, Link *q)
{
	Link p;

	p = L->head;
	while(p->next != L->tail)
		p = p->next;
	*q = p->next;
	p->next = NULL;
	L->len --;
	L->tail = p;
	return OK;
}

//已知p指向线性链表L中的一个结点，将s所指结点插入在结点p所指结点之前，并修改指针p指向新结点
Status InsBefore(LinkList *L, Link *p, Link s)
{
	Link q;

	q = L->head;
	while ((q->next != *p) && (q->next != NULL))
		q = q->next;
	if (q->next == NULL)
		return ERROR;
	if (!InsFirst(q, s))
		return ERROR;
	*p = q->next;
	L->len ++;
	return OK;
}

//已知p指向线性链表L中的一个结点，将s所指结点插入在结点p所指结点之后，并修改指针p指向新结点
Status InsAfter(LinkList *L, Link *p, Link s)
{
	s->next = (*p)->next;
	if (L->tail == *p)
		L->tail = s;
	(*p)->next = s;

    L->len ++;
    return OK;
}

//已知p指向线性链表中的一个结点，用e更新p所指结点中数据元素的值
Status SetCurElem(Link *p, ElemType e)
{
	(*p)->data = e;
	return OK;
}

//已知p指向线性链表中的一个结点，返回p所指结点中的元素数据的值
ElemType GetCurElem(Link p)
{
	return (p->data);
}

//若线性链表L为空表，则返回TRUE，否则返回FALSE
Status ListEmpty(LinkList L)
{
	if (L.len)
		return FALSE;
	else
		return TRUE;
}

//返回线性链表L中元素个数
int ListLength(LinkList L)
{
	return L.len;
}

//返回线性链表L中头结点位置
Position GetHead(LinkList L)
{
	return L.head;
}

//返回线性链表L中尾结点位置
Position GetLast(LinkList L)
{
	return L.tail;
}

//已知p指向线性链表L中的一个结点，返回p所指结点的直接前驱位置，若无前驱，则返回NULL
Position PriorPos(LinkList L, Link p)
{
	Link q;

	q = GetHead(L);
	if (q->next == p)
		return NULL;
	while((q->next != p) && (q->next != NULL))
	{
		q = q->next;
	}
	if (q->next == NULL)
		return NULL;		//未找到p
	if (q->next == p)
		return q;
	return NULL;		//我知道这里估计怎么也执行到的，为了看着舒服还是加上来了。
}

//已知p指向线性链表L中的一个结点，返回p所指结点的直接后继位置，若无后继，则返回NULL
Position NextPos(LinkList L, Link p)
{
	Link q;

	if (p == L.tail)
		return NULL;
	q = L.head;
	while((q != p) && (q->next != NULL))
	{
		q = q->next;
	}
	if (q->next == NULL)
		return NULL;	//未找到p
	if (q == p)
		return q->next;
	return NULL;
}

//返回p指向线性链表L中第i个结点的位置并返回OK，i值不合法时返回ERROR
Status LocatePos(LinkList L, int i, Link *p)
{
	int j;
	Link q;

	if ((i < 1) || i > L.len)
		return ERROR;
	q = L.head;
	for (j = 0; j <= i; j++)
	{
		q = q->next;
	}
	(*p) = q;
	return OK;
}

//返回线性链表L中第一个与e满足函数compare()判定关系的元素的位置，若不存在这样的元素，则返回NULL
Position LocateElem(LinkList L, ElemType e, Status (*compare)(ElemType, ElemType))
{
	Link p, q;

	if (!L.len)
		return NULL;
	p = L.head->next;
	q = L.tail;
	while (p != q)
	{
		if (compare(e, p->data))
			return p;
		else
			p = p->next;
	}
	if (compare(e, p->data))
		return p;
	else
		return NULL;

}

//依次对L的每个元素调用visit()。一旦visit()失败，则操作失败。
Status ListTraverse(LinkList L,Status(*visit)(Position))
{
	Link p, q;
	int i = 1;

	if (!L.len)
	{
		printf("have no elem\n");
		return ERROR;
	}

	p = L.head;
	q = L.tail;
	while(p != q)
	{
		p = p->next;
		printf("the  %dst ", i);
		if (!visit(p))
			return ERROR;
		i++;
	}
	return OK;
}


//算法2.20 在带头结点的单链线性表L的第i个元素之前插入元素e
Status ListInsert_L(LinkList *L, int i, ElemType e)
{
	Link h, s;

	if (!LocatePos(*L, i - 1, &h))
		return ERROR;
	if (!MakeNode(&s, e))
		return ERROR;
	InsFirst(h, s);
	L->len ++;
	return OK;
}


//算法2.21 将两个有序链表合并为一个有序链表
Status MergelList_L(LinkList *La, LinkList *Lb, LinkList *Lc, Status (*compare)(ElemType, ElemType))
{
	Link ha, hb, pa, pb, q;
	ElemType a, b;

	if(!InitList(Lc))
		return ERROR;
	ha = GetHead(*La);
	hb = GetHead(*Lb);
	pa = NextPos(*La, ha);
	pb = NextPos(*Lb, hb);
	while(pa && pb)
	{
		a = GetCurElem(pa);
		b = GetCurElem(pb);
		if ((*compare)(a, b))	//a<=b
		{
			DelFirst(ha, &q);
			Append(Lc, q);
			pa = NextPos(*La, ha);
		}
		else
		{
			DelFirst(hb, &q);
			Append(Lc, q);
			pb = NextPos(*Lb, hb);
		}
	}
	if (pa)
		Append(Lc, pa);
	else
		Append(Lc, pb);
	FreeNode(ha);
	FreeNode(hb);
	return OK;
}


//打印元素值
Status PriElem(Position p)
{
	printf("elem is %d\n", p->data);
	return OK;
}


Status Les(ElemType e1, ElemType e2)
{
	return(e1 < e2);
}
